package org.leetcode.middle.leetcode34;

public class Solution
{

    public  int[] searchRange2(int[] nums, int target){
        int [] res =new int[2];
        int left =search(nums,target);
        int right =search(nums,target+1)-1;

        if (left==nums.length || nums[left]!=target){
            res[0]=-1;
            res[1]=-1;
        }else {
            res[0]=left;
            res[1]=right;
        }
        return res;
    }


    private int search(int [] nums,int target){

        int left = 0;
        int right = nums.length-1;

        while (left<=right){
            int mid = (left+right)>>>1;
            if (target<=nums[mid]){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }

        return left;
    }


    public static int[] searchRange(int[] nums, int target)
    {
        int left =0,right = nums.length-1;

        int []result=new int[2];

        while (left<=right)
        {
            int mid = (left+right)>>>1;
            if (target<=nums[mid])
            {
                right=mid-1;
            }else
            {
                left=mid+1;
            }
        }

       result[0]=left;

        if (left>nums.length-1||target!=nums[left])
        {
            result[0]=-1;
            result[1]=-1;
            return result;
        }

        for (; left < nums.length; left++) {
            if (target==nums[left])
            {
                result[1]=left;
            }else
            {
                return result;
            }
        }

        return result;
    }


    public static void main(String[] args) {
//        int []nums = {5,7,7,8,8,8,10,10,13};

        int []nums = {};
        int[] result = searchRange(nums, 0);
        System.out.println(result[0]+"  "+result[1]);
    }
}
